package com.yileiqian.alg;

import java.util.Random;

/**
 * 
 * @author yileiqia
 * 
 */
public class SortAlgorithm {

	private static Random random = new Random();

	public static int[] bubbleSort(int[] array) {
		for (int i = 0; i < array.length - 1; i++) {
			for (int j = i + 1; j < array.length; j++) {
				if (array[i] > array[j]) {
					int temp = array[i];
					array[i] = array[j];
					array[j] = temp;
				}
			}
		}
		return array;
	}

	public static int[] selectionSort(int[] array) {
		for (int i = 0; i < array.length - 1; i++) {
			int min = i;

			for (int j = i + 1; j < array.length; j++) {
				if (array[j] < array[min]) {
					min = j;
				}
			}

			if (i != min) {
				int temp = array[i];
				array[i] = array[min];
				array[min] = temp;
			}
		}
		return array;
	}

	public static int[] insertSort(int[] array) {
		for (int i = 1; i < array.length; i++) {
			for (int j = i; j > 0; j--) {
				if (array[j] < array[j - 1]) {
					int temp = array[j - 1];
					array[j - 1] = array[j];
					array[j] = temp;
				} else {
					break;
				}
			}

		}
		return array;
	}

	public static int[] mergeSort(int[] array) {
		int[] temp = new int[array.length];
		buttomDownMerge(array, temp, 0, array.length - 1);
		return array;
	}

	private static void buttomDownMerge(int[] array, int[] temp, int left,
			int right) {
		if (left == right) {
			return;
		} else {
			int mid = left + (right - left) / 2;
			buttomDownMerge(array, temp, left, mid);
			buttomDownMerge(array, temp, mid + 1, right);

			for (int i = left; i <= right; i++) {
				temp[i] = array[i];
			}

			int p1 = left;
			int p2 = mid + 1;
			int i = left;

			while (p1 <= mid && p2 <= right) {
				if (temp[p1] < temp[p2]) {
					array[i++] = temp[p1++];
				} else {
					array[i++] = temp[p2++];
				}
			}

			while (p1 <= mid) {
				array[i++] = temp[p1++];
			}

			while (p2 <= right) {
				array[i++] = temp[p2++];
			}

		}
	}

	public static int[] heapSort(int[] array) {
		buildMaxHeap(array);
		for (int i = array.length; i > 1; i--) {
			int temp = array[0];
			array[0] = array[i - 1];
			array[i - 1] = temp;
			maxHeapify(array, 1, i - 1);
		}
		return array;
	}

	private static void buildMaxHeap(int[] array) {
		for (int i = array.length / 2; i > 0; i--) {
			maxHeapify(array, i, array.length);
		}
	}

	private static void maxHeapify(int[] array, int root, int size) {
		int left = root * 2;
		int right = root * 2 + 1;
		int largest = root;

		if (left <= size && array[left - 1] > array[root - 1]) {
			largest = left;
		}
		if (right <= size && array[right - 1] > array[largest - 1]) {
			largest = right;
		}
		if (largest != root) {
			int temp = array[root - 1];
			array[root - 1] = array[largest - 1];
			array[largest - 1] = temp;
			maxHeapify(array, largest, size);
		}

	}

	public static int[] quickSort(int[] array, int left, int right) {
		if (left < right) {
			int index = partition(array, left, right);
			quickSort(array, left, index - 1);
			quickSort(array, index, right);
		}
		return array;
	}

	private static int partition(int[] array, int left, int right) {
		int pivot = array[left + random.nextInt(right - left + 1)];
		while (left <= right) {
			while (array[left] < pivot) {
				left++;
			}
			while (array[right] > pivot) {
				right--;
			}
			if (left <= right) {
				swap(array, left, right);
				left++;
				right--;
			}
		}
		return left;
	}

	private static void swap(int[] array, int i, int j) {
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}

	public static int quickSelect(int[] array, int left, int right, int index) {
		if(left == right){
			return array[left];
		}
		int i = partition(array, left, right);
		if (i > index) {
			return quickSelect(array, left, i - 1, index);
		} else if (i < index) {
			return quickSelect(array, i, right, index);
		} else {
			return array[i];
		}
	}

	public static int[] clone(int[] array) {
		int[] newArray = new int[array.length];
		for (int i = 0; i < array.length; i++) {
			newArray[i] = array[i];
		}
		return newArray;
	}

	public static void print(int[] array) {
		for (int i : array) {
			System.out.print(i + " ");
		}
		System.out.println();
	}

	public static void main(String args[]) {
		int[] unsortedlist = { 9, 1, 6, 25,62,62,62,62,62,62,62,62, 62, 67, 25, 63, 78, 432, 6, -1, 2,
				0, 7, 111111111, -11111 };

		System.out.print("bubbleSort: ");
		print(bubbleSort(clone(unsortedlist)));

		System.out.print("selectionSort: ");
		print(selectionSort(clone(unsortedlist)));

		System.out.print("insertSort: ");
		print(insertSort(clone(unsortedlist)));

		System.out.print("mergeSort: ");
		print(mergeSort(clone(unsortedlist)));

		System.out.print("heapSort: ");
		print(heapSort(clone(unsortedlist)));

		System.out.print("quickSort: ");
		print(quickSort(clone(unsortedlist), 0, unsortedlist.length - 1));

		System.out.print("quickSelect: ");
		System.out.println(quickSelect(clone(unsortedlist), 0,
				unsortedlist.length - 1, 12));
	}
}
